题目分析

这个题目求解有一定的难度，能算作中等难度的题型。但是这个题目列为困难主要是在于如何在满足时间的要求下解答出来。小伙伴们先思考如何如何求解，然后再去优化它。

动态规划

这种题目可以先尝试使用动态规划进行求解。dp[i]代表前i个字符使用字典中的单词组成的结果。因此计算dp[i]时，j要遍历从0到i - 1的所有情况，如果从j到i的单词在字典中，那么dp[i]可以由dp[j]中的所有结果后面添加该单词组成。

如示例中”catsanddog”字符串，当i=7时，求解dp[7]，j从0遍历到i - 1，j=3时，dp[3]=[“cat”]是已知的，而且从第四个字符到第七个字符为”sand”在字典中，因此dp[7]可以由dp[3]在后面添加”sand”组成，此时dp[7]=[“cat sand”]。j=4时，dp[4]=[“cats”]是已知的，而且从第五个字符到第七个字符为”and”在字典中，因此dp[7]可以由dp[4]在后面添加”and”组成，此时dp[7]=[“cat sand”, “cats and”]。

这样求解是没有问题的，但是这个题目会TLE，主要问题在于浪费了大量的计算时间。举一个极端的例子。
字符串为”aaaaaa”，字典为[“a”, “aa”, “aaa”, “aaaa”, “aaaaa”, “aaaaaa”]。时间会浪费在什么地方呢？

以”aaa”结尾的只需要计算一次即可，因为以”aaa”结尾的可以是[“a aa”，”aa a”，”a a a”]，直接获取即可。但是计算dp[3]，dp[4]，dp[5]，dp[6]都没有利用到这个性质，因此不是最优解。

算法的**时间复杂度为$O(n^n)$，空间复杂度为$O(n^n)$**。

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        lens = len(s)
        wordDict = set(wordDict)
        dp = [[] for _ in range(lens + 1)]
        dp[0].append('')
        for i in range(1, lens + 1):
            for j in range(i):
                if s[j: i] in wordDict:
                    tmp = dp[j][:]
                    for k in range(len(tmp)):
                        tmp[k] += ' ' + s[j: i] if tmp[k] else s[j: i]
                    dp[i] += tmp
        return dp[-1]

DFS

DFS的思想和DP基本相同，也是判断前面的字符是否存在于字典中，如果存在则加入字符串中，并且继续寻找接下来的字符是否存在于字典中，代码非常简单，因为dp[7]需要用到dp[3]的数据，因此动态规划需要进行数据拷贝，而DFS不需要数据拷贝，只需要进入下一层栈空间即可，因此代码量相对较少，思路也比较清晰。

算法的**时间复杂度为$O(n^n)$，空间复杂度为$O(2^n)$**。

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        def dfs(s, cur):
            if not s:
                res.append(cur[1:])
                return
            for word in wordDict:
                if s[:len(word)] == word:
                    dfs(s[len(word):], cur + ' ' + word)
        res = []
        dfs(s, '')
        return res

优化DFS

虽然DFS更加简单，但是本质上并没有降低算法的时间复杂度，仍然存在着大量的冗余计算过程。

那么如何进行优化呢？我们发现DFS算法在一个极端的例子。字符串为”aaaaaa”，字典为[“a”, “aa”, “aaa”, “aaaa”, “aaaaa”, “aaaaaa”]时。cur=[“a a a”]，s=”aaa”和cur=[“a”, “aa”]，s=”aaa”的时候，都需要迭代计算s。其实无论是哪种情况，迭代s返回的结果都一样，因此不需要重复计算。

这时我们就要利用记忆化的思路，保存计算的中间结果。传递的参数为字符串的位置，当传入相同的位置时，只需要计算一次即可。

算法的**时间复杂度为$O(2^n)$，空间复杂度为$O(2^n)$**。

from functools import lru_cache


class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        @lru_cache(None)
        def dfs(index):
            if index >= len(s):
                return ['']
            cur = []
            for word in wordDict:
                if s[index: index + len(word)] == word:
                    next = dfs(index + len(word))
                    cur += [word + ' ' + x for x in next]
            return cur

        return [x[:-1] for x in dfs(0)]

刷题总结

记忆化是非常重要的考察内容之一，在DFS中十分常见，普通的DFS难度较小，因此增加记忆化提高难度，也符合现在笔试面试的要求。